Many system and/or integrated circuit applications can include a number of signals that can be placed into one or more states. It can be useful in some applications to determine when two or more signals are activated. One such application is a content addressable memory (CAM).
A typical CAM can store a number of data values in a CAM cell array. In a match operation, the data values can be compared to a comparand value (also referred to as a "search key"). A data value that matches the comparand value can result in a match indication. For some applications it can be desirable to determine when more than one match indication is generated. Such a determination can indicate an error condition, or the need to activate a priority circuit to select from among the multiple match indications. In this way, multiple match indications can be advantageous if used in (or in conjunction with) a CAM device.
A current common application for a CAM and CAM devices is in network hardware that routes and/or switches network data packets. As just one example, a router and/or network switch can use a matching function to match packet-processing criteria with information in a packet header. The packet can then be processed accordingly. "High-Traffic" routers and/or network switches can process thousands of packets in only a short amount of time. Accordingly, in order to reduce the overall packet processing time, it can be desirable to reduce the time for various CAM functions. One such function can be a multiple match detect function.
A multiple match detect function can have a number of applications in a CAM. As one example, a CAM can include an "occupied bit" for each entry that can indicate if an entry contains valid data. A multiple match detect circuit can indicate when there are more than a minimum number of occupied entries. In the event the minimum number of unoccupied entries falls below the minimum value, the CAM can provide an indication that it is almost "full." A typical CAM can include match lines that can each provide a match indication for a given data value. In order to determine a multiple match condition, the various match lines of a CAM can be monitored to determine when more than one match indication is generated.
A straightforward logical combination could include the approach set forth below. EQU MM=M1*M2+M1*M3+M2*M3
Where MM indicates a multiple match condition when high, and M1 to M3 represent the various match indications. The match indications are assumed to be active when high. Thus, utilizing the logical combination of match indication pairs, three logic pairs are required for a multiple match detection function. This approach can be generalized into the following relationship ##EQU1##
where "n" is the number of match lines, and "Pairs" is the number of match pair combinations that can be required to detect a multiple match indication.
While the conventional logical approach set forth above can be implemented for smaller numbers of match indications, such an approach is not always practical for the large number of match indications generated in higher density CAMs. Some CAM architectures can include one or more sectors, with each sector having a large number of match lines. A conventional logic approach for such a large number of match lines can be prohibitively large to implement and/or add too much delay to a multiple match function. As just one example, a sector having 2048 match lines could require the logical combination of 2,096,128 match indication pairs. If two-input logic gates (such as NAND, AND, OR or NOR gates) are used, 2,096,128 such gates could be required just to accomplish the initial AND function. It is understood that larger input logic gates could be employed, but such larger input logic gates have a proportional or correspondingly larger number of active devices (such as transistors).
Another approach for multiple match detection is a "wire-NOR" (or "wire-OR") type circuit. One example of a wire-NOR approach to multiple match detection is set forth in FIG. 5. The multiple match detect circuit is designated by the general reference character 500 and is shown to include a detect node 502 (a "wire") having a number of corresponding detect devices 504-1 to 504-n. Each detect device (504-1 to 504-n) can be activated by a corresponding match indication (M1 to Mn). When activated, a detect device (504-1 to 504-n) can couple the detect node 502 to a predetermined voltage. In the particular case of FIG. 5, each detect device (504-1 to 504-n) can discharge the detect node 502 to a lower power supply voltage VSS when activated. The detect devices (504-1 to 504-n) can be n-channel insulated gate field effect transistors (referred herein as "MOS" transistors) of the same size (i.e., having the same size channel width and length).
Also included in FIG. 5 is a detect load 506. A detect load 506 can help to maintain the detect node 502 above a predetermined potential, provided one, or none of the detect devices (504-1 to 504-n) is activated. However, in the event more than one detect device (504-1 to 504-n) is activated, the detect node 502 may be driven below a predetermined potential, and thereby detect a multiple match condition. The detect load of FIG. 5 is a p-channel MOS transistor, with a reference voltage VREFP applied to its gate.
In the particular arrangement of FIG. 5, a multiple match indication can be generated when the detect node 502 potential is driven a predetermined amount below a reference voltage VREF. The VREF voltage can be generated on a reference node 508 by a reference device 510 and a reference load 512. In FIG. 5, the reference load 512 can "match" the detect load 506. In FIG. 5, a matching reference load 512 can be formed with a transistor having the same size, and receiving the same reference voltage (VREFP) at its gate.
A response that distinguishes between a one match indication and multiple match indications can be accomplished by sizing the reference device 510. In the particular case of FIG. 5, this can be accomplished by using a transistor having the same channel length, but 1.5 times the channel width of the detect device (504-1 to 504-n) transistors.
To better understand the operation of the circuit of FIG. 5, a timing diagram is set forth in FIG. 6. FIG. 6 illustrates three different responses at the detect node 502 according to different match indication results. Response 600 represents an operation in which one match indication is generated. Consequently, one detect device (504-1 to 504-n) is activated. However, due to the detect load 506, the single activated detect device cannot "overpower" the detect load 506, and the detect node 502 remains above the VREF potential at time t0.
Response 602 represents an operation in which two match indications are generated. Consequently, two detect devices (504-1 to 504-n) are activated. The two activated detect device can discharge the detect node 502 to a voltage that is below the VREF voltage generated on the reference node 508. Thus, if the detect node 502 voltage&gt;VREF, there is no multiple match. However, if the detect node 502 voltage&lt;VREF, a multiple match condition exists. At time t0, the potential between the detect node 502 and the reference node 508 can reach a value Vdiff. This value can be used by other circuits to determine a multiple match condition.
Response 604 represents an operation in which three match indications are generated. With three detect devices (504-1 to 504-n) activated, the detect node 502 can be discharged at a faster rate, and hence develop a Vdiff potential between the detect node 502 and the reference node 508 in a shorter amount of time.
Other variations on the approach set forth in FIG. 5 can include precharge techniques, where the detect node and/or reference node can be precharged to a potential prior to the generation of match indications.
While the multiple match detect approach of FIG. 5 can be implemented with a smaller overall circuit than the previously described conventional logic approach, it is still desirable to provide a multiple match detect circuit that may have an even more rapid response.